package arithmetic.ispalindrome;

/**
 * @author zhangzg
 * 回文链表:
 * 偶数节点个数-- 1->2->3->3->2->1
 * 奇数节点个数-- 1->2->3->2->1
 *
 * 使用双节点+反转列表
 *
 * 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
 * @date 2022/11/1
 */
public class Test {

    public static void main(String[] args) {

    }

    /**
     * 快慢指针双节
     * @param head
     * @return
     */
    public static boolean isPalindrome(ListNode head){
        ListNode fast=head,slow=head;
        while (fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //链表是奇数节点个数
        if(fast!=null){
            slow=slow.next;
        }
        //慢指针的剩余链表进行反转链表操作
        slow=reverse(slow);
        //快指针还原
        fast=head;
        while (slow!=null){
            if(slow.val!= fast.val){
                return false;
            }
            slow=slow.next;
            fast=fast.next;
        }
        return true;
    }

    private static ListNode reverse(ListNode head) {
        ListNode preNode=null;
        ListNode curNode=head;
        while (curNode!=null){
            ListNode next=curNode.next;
            curNode.next=preNode;
            preNode=curNode;
            curNode=next;
        }
        return preNode;
    }

}



class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
